package com.arong.list.arrayList;

import com.arong.list.ArongList;
import jdk.nashorn.internal.runtime.regexp.joni.exception.InternalException;
import sun.misc.SharedSecrets;

import java.io.Serializable;
import java.util.*;

/**
 * 实现了四个接口（jdk8中是继承了AbstractList抽象类，为了简便，直接选择实现list接口）
 *  ArongList<E> 自定义抽象类，实现集合的增删改查功能
 *  RandomAccess 表明其支持快速（通常是固定时间）随机访问 仅仅是声明的作用，所以是空接口（用了java原包中的）
 *  Serializable 同上，是一个声明式接口，表示可以支持序列化
 *  Cloneable 使用clone()方法的时候会检查有无实现该类，没有则报异常
 * @param <E>
 *
 *     继承了AbstractList抽象类 大幅度减少迭代遍历相关的代码
 */
public class ArongArrayList<E> implements
        ArongList<E>, RandomAccess, Serializable, Cloneable {

    // 记录修改次数，尽大可能的保证线程安全(在AbstractList抽象类)
    public static int modCount;
    
    // 底层存储结构，数组（transient关键字表示不参与序列化）
    transient Object[] elementData;

    // 已使用的数组大小（即实际元素个数），而内存空间中真正占用的大小为 elementData.length
    public int size;

    // 共享空数组对象，供构造使用
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 构造方法1 传入参数为容量大小
    public ArongArrayList(int initialCapacity) {
        // 如果初始化容量大于0， 那么就创建大小为规定容量的object[]数组
        if(initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 初始化容量为0，使用共享空数组对象
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 即数组小于0的情况，抛出异常
            throw new IllegalArgumentException("数组初始化容量错误,initialCapacity = " + initialCapacity);
        }
    }

    // 构造方法2 传入参数为集合
    public ArongArrayList(Collection<? extends E> c) {
        // 先转换为 Object 数组
        elementData = c.toArray();
        if((size = elementData.length) != 0) {
            // JDK 8 会产生类型转换异常，而 jdk9+ 则不会产生
            if(elementData.getClass() != Object[].class) {
                // 如果类型不相等，则复制(本质：创建新的数组)给一个新的 Object 数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
            }
        } else {
            // 初始化容量为0，使用共享空数组对象
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

    // 构造方法3 无参构造方法

    // 默认初始化容量
    private static final int DEFAULT_CAPACITY = 10;

    // 另一个共享空数组对象，主要用于第一次创建；和前面的区分开来
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    public ArongArrayList() {
        // 懒汉式加载，创建出来的时候为空，第一次使用才赋值10
        // 两个共享空数组对象分开来是因为扩容的起点不同
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 添加元素
    @Override
    public void add(E e) {
        // 增加数组修改次数
        modCount++;
        // 如果元素刚好满了，则触发扩容机制
        final int s;
        if((s = size) == elementData.length) {
            elementData = grow();
        }
        // 末尾添加元素，数组元素长度+1
        elementData[size] = e;
        // size += 1 会产生线程安全问题 需要存储为程序内部的静态常量
        size = s + 1;
    }

    // 指定位置添加元素
    @Override
    public void add(int index, E e) {
        // 校验位置是否越界
        rangeCheckForAdd(index);
        // 增加数组修改次数
        modCount++;
        final int s;
        Object[] elementData;
        // 先赋值后判断的语句，如果数组大小不够，触发扩容
        if((s = size) == (elementData = this.elementData).length) {
            elementData = grow();
        }
        /** 复制数组往后挪动
         * System.arraycopy(
         *     @NotNull  Object src,  需要复制的源数组
         *     int srcPos,  开始复制的位置(索引)
         *     @NotNull Object dest,    复制到的目标数组
         *     int destPos, 复制到目标数组的起始索引
         *     int length   复制的长度
         *     )
         */
        System.arraycopy(elementData, index,
                elementData, index + 1,
                s - index);
        // 设置到指定位置
        elementData[index] = e;
        // size += 1 会产生线程安全问题
        size = s + 1;
    }

    // 校验位置是否在数组范围内
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("数组越界，index：" + index);
    }

    // 多个元素添加（避免多次不必要的扩容）
    public boolean addAll(Collection<? extends E> c) {
        // 将集合转换为数组
        Object[] a = c.toArray();
        // 记录变换
        modCount++;
        // 如果为空 则无意义
        int len = a.length;
        if(len == 0) {
            return false;
        }
        // 容量是否足够
        Object[] o;
        final int s;
        if(len > (o = this.elementData).length - (s = size)) {
            // 进行扩容
            grow(len + size);
        }
        // 复制数组到新的位置
        System.arraycopy(a, 0, o, size, len);
        // 数组大小的变换
        size = len + s;
        return true;
    }

    // 多个元素添加到指定位置（避免多次不必要的扩容）
    public boolean addAll(int index, Collection<? extends E> c) {
        // 校验位置是否在数组范围内
        rangeCheckForAdd(index);

        // 转换成数组
        Object[] a = c.toArray();
        // 修改次数
        modCount++;
        // 判断是否为空
        int len = a.length;
        if(len == 0) {
            return false;
        }
        // 判断是否需要扩容
        Object[] o;
        final int s;
        if(len > (o = this.elementData).length - (s = size)) {
            grow(len + size);
        }
        // 指定位置添加的差异点【！】
        if(index >= size) {
            System.arraycopy(a, 0, elementData, size, len);
        } else {
            // 被截断后后半段数组开始的位置(size + len(总长) - index - len)
            int post = s - index;
            // 原来的数组腾出空间
            System.arraycopy(elementData, index,
                    elementData, index + len,
                    post);
            // 添加新数组
            System.arraycopy(a, 0, elementData, index, len);
        }

        size = s + len;
        return true;
    }

    /**
     * 查找单个元素
     * @param o 元素值
     * @return
     */
    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, 0, size);
    }

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    int lastIndexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        // o 为 null 的情况
        if (o == null) {
            for (int i = end - 1; i >= start; i--) { // 倒序
                if (es[i] == null) {
                    return i;
                }
            }
            // o 非 null 的情况
        } else {
            for (int i = end - 1; i >= start; i--) { // 倒序
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }

        // 找不到，返回 -1
        return -1;
    }

    private int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        // o 为 null 的情况
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
            // o 非 null 的情况
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        // 找不到，返回 -1
        return -1;
    }

    /**
     * 获取指定位置的元素
     * @param index 索引
     * @return
     */
    @Override
    public E get(int index) {
        // 校验位置是否在数组范围内
        rangeCheckForAdd(index);
        return elementData(index);
    }

    /**
     * 设置指定位置的元素
     * @param index 索引
     * @param element 设置后的元素值
     * @return
     */
    public E set(int index, E element) {
        // 校验位置是否在数组范围内
        rangeCheckForAdd(index);
        // 获得 index 位置的原元素
        E oldValue = elementData(index);
        // 修改 index 位置为新元素
        elementData[index] = element;
        // 返回 index 位置的原元素
        return oldValue;
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 根据元素索引删除元素
     * @param index 元素索引
     * @return 元素值
     */
    @Override
    public E remove(int index) {
        // 校验位置是否在数组范围内
        rangeCheckForAdd(index);

        Object[] o = this.elementData;
        // 记录该位置的原值 直接用数组快速定位即可
        // @SuppressWarnings 用于抑制编译器产生警告信息（这里主要是空指针）
        @SuppressWarnings("unchecked")
        E oldValue = (E) o[index];
        // 快速移除
        fastRemove(o, index);

        return this.get(index);
    }

    /**
     * 根据元素值删除元素
     * @param e 元素值
     * @return 是否删除成功（有无对应的值）
     */
    @Override
    public boolean remove(E e) {
        Object[] o = this.elementData;
        final int size = this.size;
        int i = 0;
        found: {
            // 为空的情况分开来是因为equals会导致空指针异常
            if(o == null) {
                for( ;i < size; i++) {
                    if(o[i] == null) {
                        break found;
                    }
                }
            } else {
                for( ;i < size; i++) {
                    if(o[i].equals(e)) {
                        break found;
                    }
                }
            }
            // 如果没有找到 返回false
            return false;
        }
        // 找到索引，同上
        fastRemove(o, i);
        return true;
    }

    // 快速移除
    private void fastRemove(Object[] o, int index) {
        // 增加修改次数
        modCount++;
        // 不是末尾的元素则向前挪动
        final int s;
        if(index < (s = size - 1)) {
            System.arraycopy(o, index + 1,
                    o, index,
                    o.length - index);
        }
        // 将新的末尾置为 null ，帮助 GC
        o[size = s] = null;
    }

    /**
     * 删除多个元素
     * @param fromIndex 起始位置
     * @param toIndex 结束位置
     */
    protected void removeRange(int fromIndex, int toIndex) {
        // 参数校验
        if(fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(
                    fromIndex, toIndex));
        }
        // 增加数组修改次数
        modCount++;
        // 移除元素方法封装
        shirtTailOverGap(elementData, fromIndex, toIndex);
    }

    private void shirtTailOverGap(Object[] elementData, int low, int high) {
        // 移除数组（覆盖掉）
        System.arraycopy(elementData, high,
                elementData, low,
                high - low);
        // 将多余的置为空，方便GC 修改数组大小藏在循环条件中
        for(int to = size, i = (size -= high - low); i < to; i++) {
            elementData[i] = null;
        }
    }

    private static String outOfBoundsMsg(int fromIndex, int toIndex) {
        return "From Index: " + fromIndex + " > To Index: " + toIndex;
    }

    /**
     * 根据元素集合删除元素
     * @param c
     * @return
     */
    public boolean romoveAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);
    }

    /**
     * 求交集
     * @param c
     * @return
     */
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }

    /**
     * 批量移除指定的多个元素
     * @param c 操作的集合
     * @param complement 补足，表示是否保留 用于后续求交集的复用
     * @param from 起始位置
     * @param end 结束位置
     * @return
     */
    private boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
        // 校验非空
        Objects.requireNonNull(c);
        final Object[] o = elementData;
        int r;
        // 找到第一个不符合 complement 的
        for(r = from;; r++) {
            // 如果遍历到末尾还没有符合条件的，直接返回
            if(r == end) {
                return false;
            }
            // 有包含的了，结束
            if(c.contains(o[r]) != complement) {
                break;
            }
        }
        int w = r++;
        try {
            for(Object e; r < end; r++) {
                // 如果符合条件，该值则被移除
                if(c.contains(e = o[r]) == complement) {
                    // 移除方式o[w] = e, w++
                    o[w++] = e;
                }
            }
        } catch (Throwable ex) {
            // contains方法发生异常时候 删除数据
            System.arraycopy(o, r, o, w, end - r);
            w += end - r;
            throw ex;
        } finally {
            // 变换修改次数
            modCount += end - w;
            // 将数组 [w, end) 位置赋值为 null 。
            shirtTailOverGap(o, w, end);
        }
        return true;
    }

    /**
     * 转换成数组
     * @return
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 转换成数组
     * @param a
     * @return
     * @param <T>
     */
    public <T> T[] toArray(T[] a) {
        if(a.length < size) {
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        }
        System.arraycopy(elementData, 0, a, 0, size);
        if(a.length > size) {
            a[size] = null;
        }
        return a;
    }

    /**
     * 计算哈希值 注意保证修改前后计算数据无变化
     * @return
     */
    public int hashCode() {
        // 获取当前数组修改次数
        int expectedModCount = modCount;
        // 计算哈希值
        int hash = hashCodeRange(0, size);
        // 修改次数发生改变，则抛出异常（CAS）
        checkForComodification(expectedModCount);
        return hash;
    }

    private int hashCodeRange(int from, int to) {
        final Object[] o = elementData;
        if(to > o.length) {
            // 也是 fast-fail 修改异常检查
            throw new ConcurrentModificationException();
        }
        int hashCode = 1;
        for(int i = from; i < to; i++) {
            Object e = o[i];
            // 31 * i == (i << 5) - i
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }

    /**
     * fast-fail
     * @param expectedModCount
     */
    private void checkForComodification(int expectedModCount) {
        if(expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }

    public boolean equals(Object o) {
        // 如果对比的是本身，直接返回正确
        if(o == this) {
            return true;
        }
        // 如果对比的类型不是list，直接返回false
        if(!(o instanceof List)) {
            return false;
        }
        // 获得当前的数组修改次数
        final int expectedModCount = modCount;
        /**这里主要是运用的 ArrayList 可以快速随机访问的特性，
         * 如果数组是 ArrayList 的话，那么查询效率就会提升
         * 如果是其他数组，只能使用迭代器进行比较
         */
        boolean equal = (o.getClass() == ArongArrayList.class)
                ? equalsArrayList((ArongArrayList<?>) o)
                : equalsRange((List<?>) o, 0 ,size);
        // 修改次数发生改变，报错
        checkForComodification(expectedModCount);
        return equal;
    }

    private boolean equalsArrayList(ArongArrayList<?> other) {
        // 获得other数组修改次数
        final int expectedModCount = other.modCount;
        // 判断两者大小是否相等
        final int s = size;
        boolean equal;
        // 精简的表达
        if(equal = (s == other.size)) {
            Object[] otherEle = other.elementData;
            Object[] origanEle = elementData;
            // 防止比较中加入元素
            if(s > origanEle.length || s > otherEle.length) {
                throw new ConcurrentModificationException();
            }
            // 遍历比较(主要区别，可以通过数组直接获取元素进行比较)
            for(int i = 0; i < s; i++) {
                if(!Objects.equals(origanEle[i], otherEle[i])) {
                    equal = false;
                    break;
                }
            }
        }
        // 如果 other 修改次数发生改变，则抛出 ConcurrentModificationException 异常
        other.checkForComodification(expectedModCount);
        return equal;
    }

    boolean equalsRange(List<?> other, int from, int to) {
        final Object[] o = elementData;
        // 防止数组中加入元素
        if(to > o.length) {
            throw new ConcurrentModificationException();
        }

        Iterator<?> iterator = other.iterator();
        // 和上面原理大差不差，主要是用了迭代器
        for(; from < to; from++) {
            if(!iterator.hasNext() || !Objects.equals(o[from], iterator.next())) {
                return false;
            }
        }
        // 还要判断迭代器是否遍历完成
        return !iterator.hasNext();
    }

    /**
     * 清空数组
     */
    public void clear() {
        modCount++;
        final Object[] o = elementData;
        // 将数组元素置为空
        for(int i = 0; i < size; i++) {
            o[i] = null;
        }
        // 数组置为空
        size = 0;
    }


    /**
     * 序列化
     * @param s
     * @throws java.io.IOException
     */
    private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
        // 记录修改次数
        int expectedModCount = modCount;
        // 序列化非 transient 字段和非静态字段
        s.defaultWriteObject();
        // 写入 size 兼容 clone 方法
        s.writeInt(size);
        // elementData 是 transient 修饰的元素，
        // 为了防止多出的空间浪费，只需要序列化 [0, size) 之间的元素即可。
        for(int i = 0; i < size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 反序列化
     * @param s
     * @throws java.io.IOException
     * @throws ClassNotFoundException
     */
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        // 读取非静态属性、非 transient 属性
        s.defaultReadObject();
        // 读取 size ，不过忽略不用
        s.readInt();
        if (size > 0) {
            // 创建 elements 数组
            Object[] elements = new Object[size];
            // 逐个读取
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }
            // 赋值给 elementData
            elementData = elements;
        } else if (size == 0) {
            // 如果 size 是 0 ，则直接使用空数组
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }

    /**
     * 克隆数组
     * 注意克隆后的数组和原数组不共享
     * @return
     */
    public Object clone() {
        try {
            // 调用父类的克隆方法
            ArongArrayList<?> v = (ArongArrayList<?>) super.clone();
            // 拷贝一个新的数组
            v.elementData = Arrays.copyOf(elementData, size);
            // 重置修改次数
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalException(e.getMessage());
        }
    }

    /**
     * 扩容机制
     * @return
     */
    private Object[] grow() {
        // 是针对于前两种构造器使用的 EMPTY_ELEMENTDATA ，所以需要有个自定义扩容容量机制
        return grow(size + 1);
    }

    /**
     * 扩容机制
     * @param minCapacity 最小想要扩充到的容量
     * @return 扩容后的数组
     */
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        // 前两种构造器以及确实容量用完了
        if(oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = newLength(oldCapacity,
                    minCapacity - oldCapacity,
                    oldCapacity >> 1);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            // 无参构造器情况
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

    /**
     * 缩容机制
     */
    public void trimToSize() {
        // 增加修改次数
        modCount++;
        // 如果有多余的空间，则进行缩容
        if(size < elementData.length) {
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA // 大小为0直接使用空数组
                    : Arrays.copyOf(elementData, size); // 有大小，创建刚好大小的数组
        }
    }

    /**
     * 确认容量足够
     * @param minCapacity 最小容量
     */
    public void ensureCapacity(int minCapacity) {
        if(minCapacity > elementData.length // 需要的最小容量小于现有数组长度
                && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                && minCapacity <= DEFAULT_CAPACITY)) { // 需要最低比 DEFAULT_CAPACITY 的容量大
            // 增加修改次数
            modCount++;
            // 扩容
            grow(minCapacity);
        }
    }

    private static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

    /**
     * 计算新的扩容后的数组大小
     * @param oldLength 旧的数组的长度
     * @param minGrowth 自定义的最小数组大小
     * @param preGrowth 默认扩容大小1.5
     * @return 扩容后的数组
     */
    private int newLength(int oldLength, int minGrowth, int preGrowth) {
        // 新的长度为原来的1.5倍或者指定的最小扩容长度
        int prefLength = oldLength + Math.max(minGrowth, preGrowth);
        if(prefLength > 0 && prefLength < SOFT_MAX_ARRAY_LENGTH) {
            // 如果扩容后的数据合法，直接返回
            return prefLength;
        } else {
            return hugeLength(oldLength, minGrowth);
        }
    }

    // 超出长度调用的方法
    private int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // 小于0报错 报太大的错是因为二进制存储中反码和补码的原因
            throw new OutOfMemoryError(
                    "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            // 太长就取最长，可能会有越界问题出现
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            // 没有问题
            return minLength;
        }
    }
}
